﻿#define _CRT_SECURE_NO_WARNINGS 1
//区间选点
//给定 N个闭区间[ai, bi]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。
//输出选择的点的最小数量。
//位于区间端点上的点也算作区间内。
//输入格式
//第一行包含整数 N，表示区间数。
//接下来 N行，每行包含两个整数 ai, bi，表示一个区间的两个端点。
//输出格式
//输出一个整数，表示所需的点的最小数量。
//数据范围
//1≤N≤105,−10的9次方≤ai≤bi≤10的9次方
//输入样例：
//3
//- 1 1
//2 4
//3 5
//输出样例：
//2
//#include <iostream>
//#include <algorithm>
//
//using namespace std;
//const int N = 100010;
//struct Range
//{
//    int l, r;
//    bool operator<(const Range& W)const
//    {
//        return r < W.r;
//    }
//}range[N];
//
//int n;
//
//int main()
//{
//    cin >> n;
//
//    for (int i = 0; i < n; i++)
//    {
//        int l, r;
//        cin >> l >> r;
//        range[i] = { l, r };
//    }
//
//    sort(range, range + n);//排序右端点
//
//    int res = 0, ed = -2e9;//默认右端点为-2e9
//
//    for (int i = 0; i < n; i++)
//    {
//        if (range[i].l > ed)//如果左端点大于上一个区间的右端点，肯定不能覆盖
//        {
//            res++;
//            ed = range[i].r;//将右端点更新
//        }
//    }
//    cout << res << endl;
//    return 0;
//}

//题目：最大不相交点的数量
//给定 N个闭区间[ai, bi]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。
//输出可选取区间的最大数量。
//输入格式
//第一行包含整数 N，表示区间数。
//接下来 N行，每行包含两个整数 ai, bi，表示一个区间的两个端点。
//输出格式
//输出一个整数，表示可选取区间的最大数量。
//数据范围
//1≤N≤105,−10的9次方≤ai≤bi≤10的9次方
//输入样例：
//3
//- 1 1
//2 4
//3 5
//输出样例：
//2
//#include <iostream>
//#include<algorithm>
//
//using namespace std;
//
//const int N = 100010;
//struct Range
//{
//    int l, r;
//    bool operator<(const Range& W)const
//    {
//        return r < W.r;
//    }
//}range[N];
//
//int n;
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        int l, r;
//        cin >> l >> r;
//        range[i] = { l, r };
//    }
//    sort(range, range + n);//按右区间排序
//    int res = 0, ed = -2e9;
//    for (int i = 0; i < n; i++)
//    {
//        if (range[i].l > ed)//无相交
//        {
//            res++;
//            ed = range[i].r;
//        }
//    }
//    cout << res << endl;
//    return 0;
//}


//题目：区间分组
//给定 N个闭区间[ai, bi]，请你将这些区间分成若干组，使得每组内部的区间两两之间（包括端点）没有交集，并使得组数尽可能小。
//输出最小组数。
//输入格式
//第一行包含整数 N，表示区间数。
//接下来 N行，每行包含两个整数 ai, bi，表示一个区间的两个端点。
//输出格式
//输出一个整数，表示最小组数。
//数据范围
//1≤N≤105,−10的9次方≤ai≤bi≤10的9次方
//输入样例：
//3
//- 1 1
//2 4
//3 5
//输出样例：
//2
//做题思路：
//1.将所有区间按左端点从小到大进行排序
//2.从前往后处理每个区间
//判断能否将其放进某个现有的组中（用优先队列维护（即小根堆））
//（1）如果不存在这样的组，则开新租，然后再将其放进去
//（2）如果存在这样的组，将其放进去，并更新其右端点
//小根堆里存的是每个分组的最大右端点，当前要判断的区间的左端点至少要大于其中一个分组的最大右端点，才不用开新组，
//若小于/等于所有分组的最大右端点（也就是小于/等于堆顶），则需要开新组
//#include <iostream>
//#include <queue>
//#include <algorithm>
//
//using namespace std;
//
//const int N = 100010;
//
//struct Range
//{
//    int l, r;
//    bool operator<(const Range& W)const
//    {
//        return l < W.l;
//    }
//}range[N];
//
//int n;
//
//int main()
//{
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        int l, r;
//        cin >> l >> r;
//        range[i] = { l, r };
//    }
//    sort(range, range + n);
//    priority_queue<int, vector<int>, greater<int>>heap;//小根堆做法
//    for (int i = 0; i < n; i++)
//    {
//        auto r = range[i];
//        if (heap.empty() || heap.top() >= r.l)//为空就插入或者右区间大于左区间就要添加一个组
//        {
//            heap.push(r.r);
//        }
//        else
//        {
//            heap.pop();//删除
//            heap.push(r.r);//放入更大的右区间，如果有重合的组别，随便放一个组就行
//        }
//    }
//    cout << heap.size() << endl;
//    return 0;
//}
// 
// 
